/**
  @(#)$Id: AL_ListCircularSingle.h 74 2013-10-10 12:42:07Z xiaoting $
  @brief    One-way circular list is another form of one-way linked list structure, which is characterized by a pointer to the list 
  of the last one is no longer a null value, but point to the head of the linked list. So long as we know any node in the linked list 
  can be found circulating list of all other nodes.
  
			Singly linked list (single list) is a list, which is characterized by the direction of the chain links are unidirectional,
  Chain accessed through sequential reads starting from the head; linked list is constructed using pointers list; known the list of 
  nodes, as a linked list nodes is assembled; wherein each node has a pointer member variable refers to the next list node;

  @Author $Author: xiaoting $
  @Date $Date: 2013-10-10 20:42:07 +0800 (周四, 10 十月 2013) $
  @Revision $Revision: 74 $
  @URL $URL: https://svn.code.sf.net/p/xiaoting/game/trunk/MyProject/AL_DataStructure/groupinc/AL_ListCircularSingle.h $
  @Header $Header: https://svn.code.sf.net/p/xiaoting/game/trunk/MyProject/AL_DataStructure/groupinc/AL_ListCircularSingle.h 74 2013-10-10 12:42:07Z xiaoting $
 */

#ifndef CXX_AL_LISTCIRCULARSINGLE_H
#define CXX_AL_LISTCIRCULARSINGLE_H

#ifndef CXX_AL_NODE_H
#include "AL_Node.h"
#endif

///////////////////////////////////////////////////////////////////////////
//			AL_ListCircularSingle
///////////////////////////////////////////////////////////////////////////

template<typename T> 
class AL_ListCircularSingle
{
public:
	static const DWORD LISTSINGLE_POSITION_INVALID		= 0xffffffff;
	/**
	* Construction
	*
	* @param
	* @return
	* @note
	* @attention
	*/
	AL_ListCircularSingle();

	/**
	* Destruction
	*
	* @param
	* @return
	* @note
	* @attention
	*/
	~AL_ListCircularSingle();

	/**
	* Length
	*
	* @param VOID
	* @return DWORD
	* @note get the length of the list
	* @attention
	*/
	DWORD Length() const;
	
	/**
	* Find
	*
	* @param const T& tData <IN> 
	* @return DWORD
	* @note find the position of tData 
	* @attention  if not find, will be return 0xffffffff
	*/
	DWORD Find(const T& tData) const;

	/**
	* IsElement
	*
	* @param const T& tData <IN> 
	* @return BOOL
	* @note the tData  is in the list?
	* @attention
	*/
	BOOL IsElement(const T& tData) const;

	/**
	* Insert
	*
	* @param DWORD dwIndex <IN>
	* @param const T& tData <IN> 
	* @return BOOL
	* @note inset the tData  into the list at the position
	* @attention
	*/
	BOOL Insert(DWORD dwIndex,const T& tData);

	/**
	* InsertBegin
	*
	* @param const T& tData <IN> 
	* @return BOOL
	* @note inset the tData  into the list at the position
	* @attention
	*/
	BOOL InsertBegin(const T& tData);


	/**
	* InsertEnd
	*
	* @param const T& tData <IN> 
	* @return BOOL
	* @note inset the tData  into the list at the position
	* @attention
	*/
	BOOL InsertEnd(const T& tData);

	/**
	* Remove
	*
	* @param const T& tData <IN> 
	* @return BOOL
	* @note remove the tData in the list
	* @attention
	*/
	BOOL Remove(const T& tData);

	/**
	* RemoveAt
	*
	* @DWORD dwIndex <IN> 
	* @return BOOL
	* @note remove the tData in the list at the index (dwIndex)
	* @attention
	*/
	BOOL RemoveAt(DWORD dwIndex);

	/**
	* IsEmpty
	*
	* @param VOID
	* @return BOOL
	* @note the list has data?
	* @attention
	*/
	BOOL IsEmpty() const;

	/**
	* Get
	*
	* @param	DWORD dwIndex <IN>
	* @param	T& tTypeOut <OUT>
	* @return BOOL
	* @note get the T at the position
	* @attention the dwIndex must is little than the list length
	*/
	BOOL Get(DWORD dwIndex, T& tTypeOut) const;

	/**
	* Set
	*
	* @param	DWORD dwIndex <IN>
	* @param	T& tTypeOut <OUT>
	* @param	const T& tData <IN>
	* @return BOOL
	* @note Replaced with the element element element on position index, and returns the old element...
	* @attention Index must in the list
	*/
	BOOL Set(DWORD dwIndex, const T& tData, T& tTypeOut);

	/**
	* Clear
	*
	* @param VOID
	* @return VOID
	* @note clear the data in the list
	* @attention all data will be clear
	*/
	VOID Clear();

protected:
private:
	/**
	* GetNodeByIndex
	*
	* @param DWORD dwIndex <IN>
	* @return AL_Node<T>*
	* @note get the const T& at the position
	* @attention the dwIndex must is little than the list length
	*/
	AL_Node<T>* GetNodeByIndex(DWORD dwIndex) const;

	/**
	*Copy Construct
	*
	* @param const AL_ListCircularSingle<T>& cAL_ListCircularSingle
	* @return
	*/
	AL_ListCircularSingle(const AL_ListCircularSingle<T>& cAL_ListCircularSingle);

	/**
	*Assignment
	*
	* @param const AL_ListCircularSingle<T>& cAL_ListCircularSingle
	* @return AL_ListCircularSingle<T>&
	*/
	AL_ListCircularSingle<T>& operator = (const AL_ListCircularSingle<T>& cAL_ListCircularSingle);

public:
protected:
private: 
	AL_Node<T>*		m_pHeader;
	DWORD			m_dwSize;
};

///////////////////////////////////////////////////////////////////////////
//			AL_ListCircularSingle
///////////////////////////////////////////////////////////////////////////
/**
* Construction
*
* @param
* @return
* @note
* @attention
*/
template<typename T> 
AL_ListCircularSingle<T>::AL_ListCircularSingle():
m_pHeader(NULL),
m_dwSize(0x00)
{
	m_pHeader = new AL_Node<T>;
	m_pHeader->m_pNext = m_pHeader;
}

/**
* Destruction
*
* @param
* @return
* @note
* @attention
*/
template<typename T> 
AL_ListCircularSingle<T>::~AL_ListCircularSingle()
{
	Clear();
	//delete the header
	if (NULL != m_pHeader) {
		delete m_pHeader;
		m_pHeader = NULL;
	}
}

/**
* Length
*
* @param
* @return
* @note get the length of the list
* @attention
*/
template<typename T> DWORD 
AL_ListCircularSingle<T>::Length() const
{
	return m_dwSize;
	/*
	if (TRUE == IsEmpty()) {
		return 0;
	}
	AL_Node<T>* pMove = NULL;
	DWORD dwCount = 1;

	pMove = m_pHeader->m_pNext;
	while (m_pHeader != pMove->m_pNext) {
		dwCount ++;
		pMove = pMove->m_pNext;
	}
	return dwCount;
	*/
}

/**
* Find
*
* @param const T& tData <IN> 
* @return DWORD
* @note find the position of tData 
* @attention  if not find, will be return 0xffffffff
*/
template<typename T> DWORD 
AL_ListCircularSingle<T>::Find(const T& tData) const
{
	if (TRUE == IsEmpty()) {
		return LISTSINGLE_POSITION_INVALID;
	}
	
	AL_Node<T>* pMove = NULL;
	DWORD dwCount = 1;

	//loop the next data;
	pMove = m_pHeader->m_pNext;
	while (m_pHeader != pMove->m_pNext) {
		if (tData == pMove->m_tData) {
			//find the data
			return dwCount-1;
		}
		dwCount ++;
		pMove = pMove->m_pNext;
	}
	
	//the end
	if (tData == pMove->m_tData) {
		//find the data
		return dwCount-1;
	}

	return LISTSINGLE_POSITION_INVALID;
}

/**
* IsElement
*
* @param const T& tData <IN> 
* @return BOOL
* @note the tData  is in the list?
* @attention
*/
template<typename T> BOOL 
AL_ListCircularSingle<T>::IsElement(const T& tData) const
{
	if (LISTSINGLE_POSITION_INVALID == Find(tData )) {
		return FALSE;
	}

	return TRUE;
}

/**
* Insert
*
* @param DWORD dwIndex <IN>
* @param const T& tData <IN> 
* @return BOOL
* @note inset the tData  into the list at the position
* @attention
*/
template<typename T> BOOL 
AL_ListCircularSingle<T>::Insert(DWORD dwIndex, const T& tData)
{
	if (dwIndex > Length()) {
		//can not insert to this position
		return FALSE;
	}
	AL_Node<T>* pInsert = new AL_Node<T>;
	pInsert->m_tData = tData;
	
	AL_Node<T>* pPre = NULL;
	//get the previous Node
	if (0x00 == dwIndex) {
		pPre = m_pHeader;
	}
	else {
		pPre = GetNodeByIndex(dwIndex - 1);
	}
	
	if ((NULL == pPre)) {
		//error
		return FALSE;
	}
	if (Length() == dwIndex){
		//end
		pPre->m_pNext = pInsert;
		pInsert->m_pNext = m_pHeader;
	}
	else {
		//among of the list
		AL_Node<T>* pIndexNode = GetNodeByIndex(dwIndex);
		if ((NULL == pIndexNode)) {
			//error
			return FALSE;
		}
		pInsert->m_pNext = pIndexNode;
		pPre->m_pNext = pInsert;
	}

	m_dwSize++;
	return TRUE;
}

/**
* InsertBegin
*
* @param const T& tData <IN> 
* @return BOOL
* @note inset the tData  into the list at the position
* @attention
*/
template<typename T> BOOL 
AL_ListCircularSingle<T>::InsertBegin(const T& tData)
{
	return Insert(0, tData);
}

/**
* InsertEnd
*
* @param const T& tData <IN> 
* @return BOOL
* @note inset the tData  into the list at the position
* @attention
*/
template<typename T> BOOL 
AL_ListCircularSingle<T>::InsertEnd(const T& tData)
{
	return Insert(Length(), tData);
}


/**
* Remove
*
* @param const T& tData <IN> 
* @return BOOL
* @note remove the tData in the list
* @attention
*/
template<typename T> BOOL 
AL_ListCircularSingle<T>::Remove(const T& tData)
{
	if (TRUE == IsEmpty()) {
		return FALSE;
	}
	
	BOOL bRemove = FALSE;
	AL_Node<T>* pMove = NULL;
	DWORD dwCount = 1;

	//loop the next data;
	pMove = m_pHeader->m_pNext;
	while (m_pHeader != pMove->m_pNext) {
		if (tData == pMove->m_tData) {
			pMove = pMove->m_pNext;
			//find the data
			bRemove = RemoveAt(dwCount-1);
			if (FALSE == bRemove) {
				return bRemove;
			}
		}
		else {
			pMove = pMove->m_pNext;
		}
		dwCount ++;
	}

	//the end
	if (tData == pMove->m_tData) {
		//find the data
		bRemove = RemoveAt(dwCount-1);
		if (FALSE == bRemove) {
			return bRemove;
		}
	}

	return bRemove;
}


/**
* RemoveAt
*
* @param DWORD dwIndex <IN> 
* @return BOOL
* @note remove the tData in the list at the index (dwIndex)
* @attention
*/
template<typename T> BOOL 
AL_ListCircularSingle<T>::RemoveAt(DWORD dwIndex)
{
	if (dwIndex > Length()) {
		//can not insert to this position
		return FALSE;
	}

	AL_Node<T>* pDelete = GetNodeByIndex(dwIndex);
	if (NULL == pDelete) {
		//error
		return FALSE;
	}

	AL_Node<T>* pPre = NULL;
	//get the previous Node
	if (0x00 == dwIndex) {
		pPre = m_pHeader;
	}
	else {
		pPre = GetNodeByIndex(dwIndex - 1);
	}

	if (NULL == pPre) {
		//error
		return FALSE;
	}
	pPre->m_pNext = pDelete->m_pNext;

	delete pDelete;
	pDelete = NULL;

	m_dwSize--;
	return TRUE;
}

/**
* IsEmpty
*
* @param
* @return BOOL
* @note the list has data?
* @attention
*/
template<typename T> BOOL 
AL_ListCircularSingle<T>::IsEmpty() const
{
	return (m_pHeader == m_pHeader->m_pNext) ? TRUE:FALSE;
}

/**
* Get
*
* @param	DWORD dwIndex <IN>
* @param	T& tTypeOut <OUT>
* @return BOOL
* @note get the T at the position
* @attention the dwIndex must is little than the list length
*/
template<typename T> BOOL
AL_ListCircularSingle<T>::Get(DWORD dwIndex, T& tTypeOut) const
{
	if (TRUE == IsEmpty()) {
		//error
		return FALSE;
	}

	if (Length()-1 < dwIndex) {
		//error
		return FALSE;
	}
	
	AL_Node<T>* pGet = GetNodeByIndex(dwIndex);
	if (NULL == pGet) {
		//error
		return FALSE;
	}
	tTypeOut = pGet->m_tData;
	return TRUE;

	/* //test code
	if (TRUE == IsEmpty()) {
		//error
		return FALSE;
	}

	if (Length()-1 < dwIndex) {
		//error
		return FALSE;
	}

	AL_Node<T>* pGet = GetNodeByIndex(dwIndex);
	if (NULL == pGet) {
		//error
		return FALSE;
	}

	AL_Node<T>* pStop = pGet;
	while(pStop != pGet->m_pNext) {
		if (m_pHeader == pGet) {
			//header no data
		}
		pGet = pGet->m_pNext;
	}
	return TRUE;
	*/
}

/**
* Set
*
* @param	DWORD dwIndex <IN>
* @param	const T& tData <IN>
* @param	T& tTypeOut <OUT>
* @return BOOL
* @note Replaced with the element element element on position index, and returns the old element...
* @attention Index must in the list
*/
template<typename T> BOOL 
AL_ListCircularSingle<T>::Set(DWORD dwIndex, const T& tData, T& tTypeOut)
{
	if (Length()-1 < dwIndex) {
		//error
		return FALSE;
	}
	
	AL_Node<T>* pSet = GetNodeByIndex(dwIndex);
	if (NULL == pSet) {
		//error
		return FALSE;
	}
	
	tTypeOut = pSet->m_tData;
	pSet->m_tData = tData;
	return TRUE;
}

/**
* Clear
*
* @param VOID
* @return VOID
* @note clear the data in the list
* @attention all data will be clear
*/
template<typename T> VOID 
AL_ListCircularSingle<T>::Clear()
{
	if (TRUE == IsEmpty()) {
		//No data,
		return;
	}

	AL_Node<T>* pDelete = NULL;
	while(m_pHeader != m_pHeader->m_pNext){
		//get the node
		pDelete = m_pHeader->m_pNext;
		m_pHeader->m_pNext = pDelete->m_pNext;
		delete pDelete;
		pDelete = NULL;
	}
	m_dwSize = 0x00;
}

/**
* GetNodeByIndex
*
* @param DWORD dwIndex <IN>
* @return AL_Node<T>* 
* @note get the const T& at the position
* @attention the dwIndex must is little than the list length
*/
template<typename T> AL_Node<T>* 
AL_ListCircularSingle<T>::GetNodeByIndex(DWORD dwIndex) const
{
	if (Length()-1 < dwIndex) {
		//error
		return NULL;
	}

	AL_Node<T>* pMove = NULL;
	DWORD dwCount = 1;

	//loop the next data;
	pMove = m_pHeader->m_pNext;
	while (m_pHeader != pMove->m_pNext) {
		if (dwCount-1 == dwIndex) {
			//get this place
			return pMove;
		}
		dwCount ++;
		pMove = pMove->m_pNext;
	}
	
	//the end
	return pMove;
}

#endif // CXX_AL_LISTCIRCULARSINGLE_H
/* EOF */
